package 图;

import org.junit.Test;

import java.util.*;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/9/10 15:39
 */
public class lc210课程表II {


    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        int []inMap = new int [numCourses] ,ans = new int[numCourses];

        for (int i = 0; i < numCourses; i++) {
            map.put(i,new ArrayList<>());
        }
        for(int nums[] : prerequisites){
            map.get(nums[1]).add(nums[0]);
            inMap[nums[0]]++;
        }
        Queue<Integer> queue = new ArrayDeque<>();
        int index = 0;
        for (int i = 0; i < numCourses; i++) {
            if(inMap[i] == 0){
                queue.add(i);
            }
        }
        while(!queue.isEmpty()){
            Integer poll = queue.poll();
            ans[index++] = poll;
            for (Integer integer : map.get(poll)) {
                if(--inMap[integer] == 0){
                    queue.add(integer);
                }
            }
        }
        // 可能 存在 环, 拓扑 序要求 无环
        if(index == numCourses){
            return ans;
        }

        return new int []{};
    }
    @Test
    public void test(){
        int nums[][]= {{1,0}};
        findOrder(2,nums);
    }
}
